package com.ry.day1129;

import java.util.*;

//答案不对
public class LC3799 {

    static class Solution {
        /**
         * @param matrix: A two-dimensional array
         * @return: An array sorted by diagonal traversal
         */
        public int[] findDiagonalOrder(List<List<Integer>> matrix) {
            int cols = matrix.get(0).size();
            for (int i = 0; i <matrix.size() ; i++) {
                cols= Math.max(cols,matrix.get(i).size());
            }
            int rows = matrix.size();

            Set<Integer> set = new HashSet<>();
            for (int i = 0; i <matrix.size() ; i++) {
                for (int j = 0; j <matrix.get(i).size(); j++) {
                    set.add(i*cols+j);
                }
            }



            List<Integer> list = new ArrayList<>();
            //共有rows+cols-1条对角线
            //先处理rows行，
            for (int i = 0; i <rows ; i++) {
                int x=i;
                int y=0;

                while (x>=0&& y< cols){
                   int idx = x*cols+y;
                   if(set.contains(idx)){
                       list.add(matrix.get(x).get(y));
                   }

                    x--;
                    y++;
                }

            }

            //再处理cols-1条对角线
            for (int i = 1; i <cols ; i++) {
                int x= rows-1;
                int y=i;
                while (x>=0 && y< cols){
                    int idx = x*cols+y;
                    if(set.contains(idx)){
                        list.add(matrix.get(x).get(y));
                    }
                    x--;
                    y++;
                }
            }


            int size = list.size();
            int[] ans = new int[size];
            for (int i = 0; i <size ; i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
        List<List<Integer>> matrix = new ArrayList<>();
        matrix.add(new ArrayList<>(Arrays.asList(1,2,3)));
        matrix.add(new ArrayList<>(Arrays.asList(4,5,6)));
        matrix.add(new ArrayList<>(Arrays.asList(7,8,9)));

        matrix.clear();

        matrix.add(new ArrayList<>(Arrays.asList(1,2,3,4,5)));
        matrix.add(new ArrayList<>(Arrays.asList(6,7,8,9)));
        matrix.add(new ArrayList<>(Arrays.asList(10,11,12)));
        matrix.add(new ArrayList<>(Arrays.asList(13,14)));
        matrix.add(new ArrayList<>(Arrays.asList(15)));

        matrix.clear();

        for (int[] ints : arr2) {
            List<Integer> tmp = new ArrayList<>();
            for (int a : ints) {
                tmp.add(a);
            }

            matrix.add(tmp);
        }
        int[] data = obj.findDiagonalOrder(matrix);
//        for (int datum : data) {
//            System.out.print(datum+" ");
//        }

        System.out.println(data.length);

        System.out.println(arr2ret.length);
    }





    public static int[][] arr2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}, {20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37}, {38, 39, 40, 41, 42, 43, 44, 45, 46, 47}, {48, 49, 50, 51, 52, 53, 54, 55, 56, 57}, {58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75}, {76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87}, {88, 89, 90, 91, 92}, {93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110}, {111, 112, 113, 114, 115, 116}, {117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135}, {136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147}, {148, 149, 150, 151, 152, 153, 154, 155}, {156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173}, {174, 175, 176, 177, 178, 179, 180, 181, 182}, {183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202}, {203, 204, 205, 206, 207, 208}, {209, 210, 211, 212, 213, 214, 215, 216, 217}, {218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237}, {238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251}, {252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270}, {271, 272, 273, 274, 275, 276, 277, 278, 279, 280}, {281, 282, 283, 284, 285, 286}, {287, 288, 289, 290, 291, 292, 293, 294, 295, 296}, {297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309}, {310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320}, {321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336}, {337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350}, {351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365}, {366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377}, {378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388}, {389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404}, {405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416}, {417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436}, {437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451}, {452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463}, {464, 465, 466, 467, 468, 469, 470}, {471, 472, 473, 474, 475, 476, 477}, {478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497}, {498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511}, {512, 513, 514, 515, 516, 517, 518, 519}, {520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535}, {536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547}, {548, 549, 550, 551, 552}, {553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570}, {571, 572, 573, 574, 575, 576, 577, 578, 579, 580}, {581, 582, 583, 584, 585, 586, 587, 588, 589, 590}, {591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610}, {611, 612, 613, 614, 615, 616, 617, 618, 619, 620}, {621, 622, 623, 624, 625}, {626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637}, {638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654}, {655, 656, 657, 658, 659, 660, 661, 662, 663, 664}, {665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676}, {677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690}, {691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705}, {706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719}, {720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736}, {737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751}, {752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762}, {763, 764, 765, 766, 767}, {768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784}, {785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799}, {800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815}, {816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831}, {832, 833, 834, 835, 836, 837, 838, 839}, {840, 841, 842, 843, 844, 845, 846, 847, 848}, {849, 850, 851, 852, 853}, {854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871}, {872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889}, {890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909}, {910, 911, 912, 913, 914}, {915, 916, 917, 918, 919, 920, 921, 922}, {923, 924, 925, 926, 927, 928, 929, 930}, {931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947}, {948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959}, {960, 961, 962, 963, 964, 965}, {966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979}, {980, 981, 982, 983, 984, 985, 986, 987, 988}, {989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000}};
    public static int[] arr2ret = {1,20,2,38,21,3,48,39,22,4,58,49,40,23,5,76,59,50,41,24,6,88,77,60,51,42,25,7,93,89,78,61,52,43,26,8,111,94,90,79,62,53,44,27,9,117,112,95,91,80,63,54,45,28,10,136,118,113,96,92,81,64,55,46,29,11,148,137,119,114,97,82,65,56,47,30,12,156,149,138,120,115,98,83,66,57,31,13,174,157,150,139,121,116,99,84,67,32,14,183,175,158,151,140,122,100,85,68,33,15,203,184,176,159,152,141,123,101,86,69,34,16,209,204,185,177,160,153,142,124,102,87,70,35,17,218,210,205,186,178,161,154,143,125,103,71,36,18,238,219,211,206,187,179,162,155,144,126,104,72,37,19,252,239,220,212,207,188,180,163,145,127,105,73,271,253,240,221,213,208,189,181,164,146,128,106,74,281,272,254,241,222,214,190,182,165,147,129,107,75,287,282,273,255,242,223,215,191,166,130,108,297,288,283,274,256,243,224,216,192,167,131,109,310,298,289,284,275,257,244,225,217,193,168,132,110,321,311,299,290,285,276,258,245,226,194,169,133,337,322,312,300,291,286,277,259,246,227,195,170,134,351,338,323,313,301,292,278,260,247,228,196,171,135,366,352,339,324,314,302,293,279,261,248,229,197,172,378,367,353,340,325,315,303,294,280,262,249,230,198,173,389,379,368,354,341,326,316,304,295,263,250,231,199,405,390,380,369,355,342,327,317,305,296,264,251,232,200,417,406,391,381,370,356,343,328,318,306,265,233,201,437,418,407,392,382,371,357,344,329,319,307,266,234,202,452,438,419,408,393,383,372,358,345,330,320,308,267,235,464,453,439,420,409,394,384,373,359,346,331,309,268,236,471,465,454,440,421,410,395,385,374,360,347,332,269,237,478,472,466,455,441,422,411,396,386,375,361,348,333,270,498,479,473,467,456,442,423,412,397,387,376,362,349,334,512,499,480,474,468,457,443,424,413,398,388,377,363,350,335,520,513,500,481,475,469,458,444,425,414,399,364,336,536,521,514,501,482,476,470,459,445,426,415,400,365,548,537,522,515,502,483,477,460,446,427,416,401,553,549,538,523,516,503,484,461,447,428,402,571,554,550,539,524,517,504,485,462,448,429,403,581,572,555,551,540,525,518,505,486,463,449,430,404,591,582,573,556,552,541,526,519,506,487,450,431,611,592,583,574,557,542,527,507,488,451,432,621,612,593,584,575,558,543,528,508,489,433,626,622,613,594,585,576,559,544,529,509,490,434,638,627,623,614,595,586,577,560,545,530,510,491,435,655,639,628,624,615,596,587,578,561,546,531,511,492,436,665,656,640,629,625,616,597,588,579,562,547,532,493,677,666,657,641,630,617,598,589,580,563,533,494,691,678,667,658,642,631,618,599,590,564,534,495,706,692,679,668,659,643,632,619,600,565,535,496,720,707,693,680,669,660,644,633,620,601,566,497,737,721,708,694,681,670,661,645,634,602,567,752,738,722,709,695,682,671,662,646,635,603,568,763,753,739,723,710,696,683,672,663,647,636,604,569,768,764,754,740,724,711,697,684,673,664,648,637,605,570,785,769,765,755,741,725,712,698,685,674,649,606,800,786,770,766,756,742,726,713,699,686,675,650,607,816,801,787,771,767,757,743,727,714,700,687,676,651,608,832,817,802,788,772,758,744,728,715,701,688,652,609,840,833,818,803,789,773,759,745,729,716,702,689,653,610,849,841,834,819,804,790,774,760,746,730,717,703,690,654,854,850,842,835,820,805,791,775,761,747,731,718,704,872,855,851,843,836,821,806,792,776,762,748,732,719,705,890,873,856,852,844,837,822,807,793,777,749,733,910,891,874,857,853,845,838,823,808,794,778,750,734,915,911,892,875,858,846,839,824,809,795,779,751,735,923,916,912,893,876,859,847,825,810,796,780,736,931,924,917,913,894,877,860,848,826,811,797,781,948,932,925,918,914,895,878,861,827,812,798,782,960,949,933,926,919,896,879,862,828,813,799,783,966,961,950,934,927,920,897,880,863,829,814,784,980,967,962,951,935,928,921,898,881,864,830,815,989,981,968,963,952,936,929,922,899,882,865,831,990,982,969,964,953,937,930,900,883,866,991,983,970,965,954,938,901,884,867,992,984,971,955,939,902,885,868,993,985,972,956,940,903,886,869,994,986,973,957,941,904,887,870,995,987,974,958,942,905,888,871,996,988,975,959,943,906,889,997,976,944,907,998,977,945,908,999,978,946,909,1000,979,947};

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3799 · 对角线遍历（二）
算法
中等
通过率
50%

题目
题解3
笔记
讨论
排名
记录
描述
给定一个二维数组 matrix，按照对角线从左下至右上，从左至右的规则（如下图）遍历二维数组，并按顺序返回 matrix 中对角线上的整数。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1
≤
m
a
t
r
i
x
.
l
e
n
g
t
h
≤
1
0
5
1≤matrix.length≤10
5

1
≤
m
a
t
r
i
x
[
i
]
.
l
e
n
g
t
h
≤
1
0
5
1≤matrix[i].length≤10
5

1
≤
m
a
t
r
i
x
[
i
]
[
j
]
≤
1
0
9
1≤matrix[i][j]≤10
9

matrix 中最多有
1
0
5
10
5
  个数字
样例
样例 1：

输入：
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
输出：
[1, 4, 2, 7, 5, 3, 8, 6, 9]
解释：
如下图
4077_1.png

样例 2：

输入：
matrix = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9],
[10, 11, 12],
[13, 14],
[15]
]
输出：
[1, 6, 2, 10, 7, 3, 13, 11, 8, 4, 15, 14, 12, 9, 5]
解释：
如下图
4077_4.png

样例 3：

输入：
matrix = [
[1, 2, 3, 4, 5],
[6, 7],
[8],
[9, 10, 11, 12],
[13, 14, 15, 16, 17]
]
输出：
[1, 6, 2, 8, 7, 3, 9, 4, 13, 10, 5, 14, 11, 15, 12, 16, 17]
解释：
如下图
4077_3.png

标签
相关题目

1205
对角线遍历
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
48/1881
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
